package E_2024;

import java.util.HashMap;
import java.util.Map;

/*
题目描述
    静态扫描可以快速识别源代码的缺陷，静态扫描的结果以扫描报告作为输出：
    文件扫描的成本和文件大小相关，如果文件大小为 N，则扫描成本为 N 个金币
    扫描报告的缓存成本和文件大小无关，每缓存一个报告需要 M 个金币
    扫描报告缓存后，后继再碰到该文件则不需要扫描成本，直接获取缓存结果
    给出源代码文件标识序列和文件大小序列，求解采用合理的缓存策略，最少需要的金币数。

输入描述
    第一行为缓存一个报告金币数：M
    第二行为文件标识序列：F1,F2,F3,....,Fn
    第三行为文件大小序列：S1,S2,S3,....,Sn
    备注：
    L ≤ M ≤ 100
    1 ≤ N ≤ 10000
    1 ≤ Fi ≤ 1000
    1 ≤ Si ≤ 10
输出描述
    采用合理的缓存策略，需要的最少金币数
 */
public class E_100_33 {
    public static void main(String[] args) {
        System.out.println(ans(new int[]{1, 2, 3}, new int[]{5, 4, 3}, 3));
        System.out.println(ans(new int[]{1, 1, 1, 1, 2, 2}, new int[]{2, 2, 2, 2, 4, 4}, 3));
    }
    public static int ans(int[] files, int[] size, int scan){
        // 记录文件出现次数
        Map<Integer,Integer> fmap = new HashMap<>();
        // 记录文件大小
        Map<Integer,Integer> smap = new HashMap<>();
        for (int i = 0; i < files.length; i++) {
            fmap.put(files[i], fmap.getOrDefault(files[i],0) + 1);
            smap.put(files[i], size[i]);
        }
        int ans = 0;
        for (Integer key : fmap.keySet()) {
            // 分别计算文件不缓存需要多少金币及文件进缓存需要多少金币，取最小值
            int a = smap.get(key) * fmap.get(key);
            int b = smap.get(key) + scan;
            ans += Math.min(a,b);
        }
        return ans;
    }
}
